package 剑指offer;

/**
 * 
 * @author 兰伟朋
 *@time 2020年12月10日下午10:53:04
 *@see
 *	一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 *答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *该题的求解和斐波那契数列的求解相似
 */
public class _10_2青蛙跳台阶问题 {
	public static void main(String[] args) {
		System.out.println(numWays(7));
	}
	  public static  int numWays(int n) {
		  int a=1,b=1,sum;
		  for (int i = 0; i < n; i++) {
			sum=a+b;
			a=b;
			b=sum%1000000007;
		}
		  if(a==1000000008)
			  return 1;
		  return a;
	    }

	  
	  
	  
	  
	  
	  
	  
	  
	  
	  
	  
	  
	  
	  
	  
	  
	  
}
